package reBuildBinaryTree;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        int[] pre = {1,2,3,4,5,6,7};
        int[] mid = {3,2,4,1,6,5,7};
        Main main = new Main();
        TreeNode head = main.solution(pre,mid);
        main.frontForTree(head);
        System.out.println("\n-----");
        head = main.solution(new int[]{1,2,4,7,3,5,6,8},new int[]{4,7,2,1,5,3,8,6});
        main.frontForTree(head);
    }
    public TreeNode solution(int[] pre , int[] middle){
        // 先从前序数组中,找到 middle 数组中的
        TreeNode head = new TreeNode(pre[indexOf(pre,middle)]);
        //找到
        int location = find(middle,head.getVar());
        if(location == 0){
            head.setLeft(null);
        }else {
            head.setLeft(solution(pre, Arrays.copyOfRange(middle,0,  location)));
        }

        location =  find(middle,head.getVar())+1;
        if( location >= middle.length){
            head.setRight(null);
        }else{
            head .setRight(solution(pre, Arrays.copyOfRange(middle,location, middle.length)));
        }
        return head ;
    }
    /*
    * 定位到根节点在中序数列中的位置
    *
    * */
    public int indexOf(int[] a , int[] b){
        for(int e = 0 ; e < a.length; e++){
            for( int ee : b){
                if( a[e] == ee){
                    return e ;
                }
            }
        }
        System.out.println(Arrays.toString(b));
        return -1 ;
    }
    /* 定位到元素在数组中的位置
    * */
    public int find(int[] a , int target){
        for(int i = 0 ; i < a.length ; i++ ) {
            if(a[i] == target){
                return i;
            }
        }
        return -1 ;
    }
    public void frontForTree(TreeNode head){
        List<TreeNode> nodes = new ArrayList<>();
        TreeNode n = null ;
        nodes.add(head);
        while(!nodes.isEmpty()){
            n = nodes.get(0);
            nodes.remove(0);
            if(null != n) {
                nodes.add(0 , n.getRight());
                nodes.add(0 , n.getLeft());
                System.out.print(n.getVar());
            };

        }
    }
}
